package com.ly.algorithm.offerpointer;

import java.util.*;

/**
 * @Classname Offer38
 * @Description
 *
 * 输入一个字符串，打印出该字符串中字符的所有排列。
 *
 *  
 *
 * 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
 *
 *  
 *
 * 示例:
 *
 * 输入：s = "abc"
 * 输出：["abc","acb","bac","bca","cab","cba"]
 *
 *
 * @Date 2021/1/30 15:33
 * @Author 冷心影翼
 */
public class Offer38 {

    public static void main(String[] args) {
        Solution38 solution38 = new Solution38();
        String[] abcs = solution38.permutation("a");
        System.out.println(Arrays.toString(abcs));
    }

}

class Solution38 {

    private Set<String> res;

    private boolean[] visited;

    public String[] permutation(String s) {
        res = new HashSet<>();
        visited = new boolean [s.length()];
        dfs(s,new StringBuilder());
        String[] r = new String[res.size()];
        Iterator<String> iterator = res.iterator();
        int i = 0;
        while (iterator.hasNext()) {
            r[i++] = iterator.next();
        }
        return r;
    }

    public void dfs(String s,StringBuilder path) {
        if(path.length() == s.length()) {
            res.add(path.toString());
            return;
        }
        for (int i = 0; i < s.length(); i++) {
            if(!visited[i]) {
                visited[i] = true;
                path.append(s.charAt(i));
                dfs(s,path);
                path.deleteCharAt(path.length()-1);
                visited[i] = false;
            }
        }
    }
}